package com.lihepeng.leecode.solid_aim_offer.array;

/**
 * 在排序数组中查找数字
 * 返回数字出现的个数
 *
 */
public class Solution53 {
    //遍历计数
    public int search(int[] nums, int target) {
        int totalCount = 0;
        for (int num : nums) {
            if (num == target){
                totalCount++;
            }
        }
        return totalCount;
    }
    // 使用二分查找
    // 确定 边界坐标

    public int search01(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums,target,false)-1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return rightIdx - leftIdx + 1;
        }
        return 0;
    }
    private int binarySearch(int[] nums, int target,boolean lower){
        int n = nums.length;
        int left =0,right = n-1,ans =n;
        while (left <= right){
            int mid = left+(right - left) /2;
            if (nums[mid] > target||(lower && nums[mid] >= target)){
                right = mid -1;
                ans = mid;
            }else {
                left = mid+1;
            }
        }

        return ans;
    }
}
